1. Field of the Invention
This invention relates to computer storage of information, and more particularly, to a method for allocating cache storage resources in a multi-echelon staged storage system with reference to prioritized data sets and weighting factors.
2. Description of the Related Art
A computer system typically includes an information processor coupled to a heirarchical staged storage system. The type of storage employed in each staging location relative to the processor is normally determined by balancing requirements for speed, capacity, and cost. Computer processes continually refer to this storage over their executing lifetimes, both reading from and writing to the staged storage system. These references include self-referencing as well as references to every type of other process, overlay or data. It is well-known in the art that data storage devices using high-speed random access memory (RAM) can be referenced orders of magnitude faster than high volume direct-access storage devices (DASD's) using rotating magnetic media. Such electronic RAM storage typically relies upon high-speed transfer of electrical charges over short distances while DASD's typically operate mechanically by rotating a data storage position on a magnetic disk with respect to read-write heads. The relative cost per bit of storage for DASD and RAM makes it necessary to use DASD for bulk storage and electronic RAM for processor internal memory and caching.
In a multi-echelon staged memory system, a cache is typically placed between a processor and a larger but slower memory device. For instance, caches employing appropriate devices are found between a processor and main memory and between main memory and a DASD. The caching technique arose from the observation that processors frequently cluster their references in time and space to small sub-sets of all data stored. Thus, if 80% of the immediate references are to 5% of the data space, then storing that popular 5% in cache significantly decreases average reference time because of the substantial access speed advantage of cache over main storage. The fundamental caching problem involves establishing an efficient scheme for allocating cache spatial and temporal resources among multiple concurrent processes and their referenced data.
When data referenced by a process is found in the cache memory, it is a "hit" and a copy of the requested data is sent to the requesting process. When the desired data is not found, it is a "miss" and the requested data is read from the larger, slower main storage device and transferred both to cache and to the requesting process. When the "miss" data is added to cache, it replaces selected data already in cache. When the replaced data is selected according to the Least Recently Used (LRU) algorithm, the cache is referred to as an LRU cache.
Where long strings of single references are made, such as to consecutive addresses defining a table, the LRU cache efficiency breaks down and the clustering advantage disappears. This is because the data not in cache must be continually staged up from the slower main storage device, resulting in continual cache "flushing". The "set-associative" cache organization scheme is an example known in the art as sometimes useful for reducing the effects of cache flushing by storing sets of sequential data of some length.
In U.S. Pat. No. 4,463,424 ("Method for Dynamically Allocating LRU-MRU Managed Memory Among Concurrent Sequential Processes", Jul. 31, 1984), Mattson, et al, disclose a method for dynamic adjustment of LRU cache partition size among a plurality of concurrent processes in a CPU as a direct function of a hit/miss ratio approximated from sampled reference traces. Mattson attempts to use hit/miss ratio to dynamically control cache space and time allocations for improved cache efficiency and to minimize the effects of flushing.
Reference should also be made to Cole, et al, U.S. Pat. No. 4,603,382, "Dynamic Buffer Reallocation", issued Jul., 29, 1986. Cole discloses an arrangement for varying the size of a tape buffer allocated to diverse tape units as a function of hit/miss ratio (data read misses or buffer full). Lastly, reference should be made to Dixon, et al, U.S. Pat. No. 4,489,378, "Automatic Adjustment of the Quantity of Pre-fetch Data in a Disk Cache Operation", issued Dec. 18, 1984. Dixon discloses a method for varying the amount of data prefetched to cache.
Cache management techniques for preserving process priority that exploit variations in reference patterns while optimizing prioritized partitioned cache performance are not known in the prior art. A method for cache space reallocation among prioritized partitions that both preserves priority and maximizes overall cache efficiency was unknown until now.